package dp.test123;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 9:13
 */
public class Solution1 {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int[][] dp = new int[n][3];
        for(int k = 1; k < 3; k++){
            for(int i = 1; i < n; i++){
                int min = Integer.MAX_VALUE;
                for(int j = 0; j < i; j++){
                    min = Math.min(min, prices[j] - dp[j][k - 1]);
                }
                dp[i][k] = Math.max(dp[i - 1][k], prices[i] - min);
            }
        }
        return dp[n - 1][2];
    }
}
